package com.lw.leetcode.back.c;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * 282. 给表达式添加运算符
 *
 * @author liw
 * @version 1.0
 * @date 2021/10/16 9:03
 */
public class AddOperators {

    public static void main(String[] args) {
        AddOperators test = new AddOperators();

        // ["1+2+3", "1*2*3"]
//        String str = "123";
//        int t = 6;

        //  ["2*3+2", "2+3*2"]
//        String str = "232";
//        int t = 8;

        //   ["1*0+5","10-5"]
//        String str = "105";
//        int t = 5;

        //   []
//        String str = "3456237490";
//        int t = 9191;



//        String str = "123456789";
//        int t = 45;

        String str = "2147483648";
        int t = -2147483648;

        List<String> list = test.addOperators(str, t);
        System.out.println(list);
    }

    private Stack<Long> stack = new Stack<>();
    private char[] ops;
    private int length = 0;
    private int[] nums;
    private int target;
    private List<String> list;
    private StringBuilder sb;

    private int r;

    public List<String> addOperators(String num, int target) {

        r = target == 0 ? 1 : 0;
        length = num.length() - 1;
        this.target = target;
        ops = new char[length];
        sb = new StringBuilder((length << 1) + 1);
        nums = new int[length + 1];
        for (int i = 0; i <= length; i++) {
            char c = num.charAt(i);
            nums[i] = c - '0';
        }
        list = new ArrayList<>();
        find(0);
        return list;
    }

    private void find(int index) {

        if (index == length) {
            long calculate = calculate();
            if (calculate == target) {
                sb.append(nums[0]);
                for (int i = 0; i < length; i++) {
                    if (ops[i] != ' ') {
                        sb.append(ops[i]);
                    }
                    sb.append(nums[i + 1]);
                }
                list.add(sb.toString());
                sb.setLength(0);
            }
            return;
        }

        ops[index] = '+';
        find(index + 1);
        ops[index] = '-';
        find(index + 1);
        ops[index] = '*';
        find(index + 1);
        ops[index] = ' ';
        find(index + 1);
    }


    private long calculate() {
        long result = 0L;
        stack.add(0L);
        stack.add((long)nums[0]);
        int flag = 0;
        for (int i = 1; i <= length; i++) {
            char op = ops[i - 1];
            int num = nums[i];
            switch (op) {
                case '+':
                    if (flag == 1) {

                        stack.push(stack.pop() * stack.pop());
                    }
                    flag = 0;
                    stack.push((long)num);
                    break;
                case '-':
                    if (flag == 1) {

                        stack.push(stack.pop() * stack.pop());
                    }
                    flag = 0;
                    stack.push((long)-num);
                    break;
                case '*':
                    if (flag == 1) {
                        stack.push(stack.pop() * stack.pop());
                    }
                    flag = 1;
                    stack.push((long)num);
                    break;
                default:
                    long peek = stack.peek();
                    if (peek == 0) {
                        stack.clear();
                        return r;
                    }
                    if (peek < 0) {
                        stack.push(stack.pop() * 10 - num);
                    } else {
                        stack.push(stack.pop() * 10 + num);
                    }

                    break;
            }
        }
        if (flag == 1) {
            stack.push(stack.pop() * stack.pop());
        }
        while (!stack.isEmpty()) {
            result += stack.pop();
        }
        return result;
    }

}
